package com.fosss.dac;

/**
 * 分治算法解决汉诺塔问题
 */
public class HanoiTower {
    private static int number=0;
    public static void main(String[] args) {
        hanoiTower(40,'A','B','C');
        System.out.println(number);
    }
    public static void hanoiTower(int num,char a,char b,char c){
        number++;
        if(num==1){
            System.out.println(a+"->"+c);
        }else {
            //当盘子的个数大于1时，总体看成两个盘（最下边的盘和其他盘）A->C A->B B->C
            //先把上边所有盘移动到B
            hanoiTower(num-1,a,c,b);
            //将最后一个盘移动到C
            System.out.println(a+"->"+c);
            //将B上的盘移动到C
            hanoiTower(num-1,b,a,c);
        }
    }
}
